package com.mypaper.list;

import com.mypaper.elem.DataElement;
import com.mypaper.elem.LinkedListNode;

public class OrderLinkedList extends LinkedListClass{
/*
 * 有序链表，用于构造空闲时间队列
 */
	public OrderLinkedList(){
		super();
	}
	public OrderLinkedList(OrderLinkedList otherList){
		super();
	}	
	
	public boolean isExisted(DataElement otherElement){
		LinkedListNode firstNode=this.first;
		while(firstNode!=null){
			if(firstNode.info.equals(otherElement)){
				return true;
			}
			firstNode=firstNode.next;
		}
		return false;
	}
	
	public DataElement search(DataElement searchItem) {
		LinkedListNode current;
		boolean found;
		current=last;
		found=false;
		while(current!=null&&!found){
			if(current.info.properSlot(searchItem)!=null)
				found=true;
			else
				current=current.next;
		}
		if(!found)
			return null;
		else{
			return current.info;
		}
	}
	
	public DataElement searchIdle(DataElement searchItem) {
		LinkedListNode current;
		boolean found;
		current=first;
		found=false;
		while(current!=null&&!found){
			if(current.info.properSlot(searchItem)!=null)
				found=true;
			else
				current=current.next;
		}
		if(!found)
			return null;
		else{
			return current.info;
		}
	}
	
	public void deleteNode(DataElement deleteItem) {
		LinkedListNode current;
		LinkedListNode trailCurrent;
		boolean found;
		if(first==null)
			System.out.println("Cannot delete from an empty list");
		else{
			current=first;
			trailCurrent=first;
			if(current.info.equals(deleteItem)){
				first=first.next;
				count--;
			}else{
				found=false;
				while(current!=null&&!found){
					if(current.info.equals(deleteItem)){
						found=true;
					}else{
						trailCurrent=current;
						current=current.next;
					}
				}
				if(current==null)
					System.out.println("The item to be deleted is not in the list.");					
				else{
					trailCurrent.next=current.next;
					count--;
				}
			}
		}
	}
	
	//插入一个空闲，若有相邻的空闲块，合并
	public void insertNode(DataElement insertItem){
		LinkedListNode current;
		LinkedListNode trailCurrent;
		LinkedListNode newNode;
		boolean found;
		
		newNode = new LinkedListNode();
		newNode.info=insertItem.getCopy();
		newNode.next=null;
		
		if(first==null){
			first=newNode;
			last=newNode;
			count++;
		}else{
			trailCurrent=first;
			current=first;
			found=false;
			while(current!=null&&!found){
				if(current.info.compareTo(insertItem)>0){
					found=true;
				}
				else{
					trailCurrent=current;
					current=current.next;
				}	
			}
			if(current==first){
				newNode.next=first;
				first=newNode;
				count++;
			}else if(current==null){
				trailCurrent.next=newNode;
				last=newNode;
				count++;
			}else{
				trailCurrent.next=newNode;
				newNode.next=current;
				count++;
			}
		}
	}		
}
